We report the discovery of Kepler-15b, a new transiting exoplanet detected by NASA's Kepler mission. The transit signal with a period of 4.94 days was detected in the quarter 1 (Q1) Kepler photometry. For the first time, we have used the High-Resolution-Spectrograph (HRS) at the Hobby-Eberly Telescope (HET) to determine the mass of a Kepler planet via precise radial velocity (RV) measurements. The 24 HET/HRS radial velocities (RV) and 6 additional measurements from the FIES spectrograph at the Nordic Optical Telescope (NOT) reveal a Doppler signal with the same period and phase as the transit ephemeris. We used one HET/HRS spectrum of Kepler-15 taken without the iodine cell to determine accurate stellar parameters. The host star is a metal-rich ([Fe/H]=0.36+/-0.07) G-type main sequence star with T_eff=5515+/-124 K. The amplitude of the RV-orbit yields a mass of the planet of 0.66+/-0.1 M_Jup. The planet has a radius of 0.96+/-0.06 R_Jup and a mean bulk density of 0.9+/-0.2 g/cm^3. The planetary radius resides on the lower envelope for transiting planets with similar mass and irradiation level. This suggests significant enrichment of the planet with heavy elements. We estimate a heavy element mass of 30-40 M_Earth within Kepler-15b.